Memoization
Learn about memoization in Python.
We'll cover the following
Memoization is a technique used to speed up function calls by caching their results. The results can be cached only if the function is pure, meaning that it has no side effects or outputs and that it does not depend on any global state.
Memoizing sin function#
A trivial function that can be memoized is the sine function sin.
The first time that memoized_sin is called with an argument that is not stored in _SIN_MEMOIZED_VALUES, the value will be computed and stored in this dictionary.
Later on, if we call the function with the same value again, the result will be retrieved from the dictionary rather than being computed another time. While sin is a function that computes very quickly, this may not be true for some advanced functions
involving more complicated computations.
Usage of memoization can be simplified in Python by using a decorator. PyPI lists a few implementations of memoization through decorators, from very simple cases to the most complex and comprehensive.
functools#
Starting with Python 3.3, the functools module provides a LRU (least recently used) cache decorator. This decorator provides the same functionality as the memoization described here, but with the benefit that it limits the number of entries in the cache, removing the least recently used one when the cache size reaches its maximum.
The module also provides statistics on cache hits, misses, etc. In my opinion, these are must-haves when implementing such a cache. There’s no point in using memoization, or any caching technique if you are unable to meter its usage and usefulness.
In the example below, you can see the implementation of the memoized_sin() function, using functools.lru_cache.
Using cachetools for memoization#
If an older version of Python is used, or if a different algorithm is desired, the
cachetools package, as seen previously, provides a useful cachetools module that can be imported with a wide variety of cache types as shown in the below example.
Since ttl=5, the cache clears out after every five seconds. So, it will only hit if you access a stored value within five seconds of storage.
Local Caching
Distributed Caching